Until recently, animated three-dimensional graphics were exclusively applied in devices with a relatively high processing power such as, for instance, in generating displays of the appearance of an object from several angles on a workstation or a PC during computer aided design and computer aided manufacture, in electronic video arcade games, or in driving- or flight simulators.
Three-dimensional graphics now also find their way into devices with a relatively low processing power such as mobile phones, personal digital assistants (PDA) and hand-held video games.
To provide animation, it is necessary to update the image at rates approaching 20 to 30 frames per second (lower rates are acceptable for some applications), so that an observer perceives the image as a continuous change rather than a chain of static images.
The speed at which the apparatus can perform calculations, coupled with the minimum acceptable frame rate, provides a limit to the number of calculations which can be performed to generate each image.
In three-dimensional animation, it is necessary to calculate for each image the projection of the three-dimensional objects on two dimensions. For complex images a large amount of calculations can be required.
Image synthesis is usually performed by representing an object as a number of polygon primitives defined by vertices, projecting the polygon primitives onto an image plane, and then processing each polygon primitive in order to define, for each pixel of the projected polygon, the pixel color.
A major problem in rendering three-dimensional graphics is the removal of hidden surfaces. From the viewpoint, the nearer surfaces should obscure the further parts.
A common approach is to test, when a given pixel is rendered, whether it lies in front (and therefore occludes) or behind, (and therefore is occluded by) the pixel (if any) which is already within the image buffer. Accordingly, each pixel needs to be assigned a depth value. This technique is referred to as the “z-buffer algorithm”. This technique is a technically simple approach, but it is resource intensive in terms of storage and processing power since it involves a large number of comparison operations (on the order of the number of pixels in the image buffer), for real time operation.
The “Painter's Algorithm” examines the coordinates of the vertices of the polygons, and ranks the polygons into order of decreasing distance from the viewpoint. The polygons are then rendered in order of decreasing distance, so that the pixels of the most distant polygons are first written into the image buffer, and are overwritten as necessary by those of nearer polygons. However, this technique requires the sorting operation of all polygons to be repeated each time the viewpoint changes, and consequently, requires a large amount of computation in real time.
In a known technique, polygons are viewed as having two faces; one face directed inwardly towards the interior of the object (the “back” face) and one face directed outwardly of the object (the “front” face). For a solid object, the “back” face of a polygon is never visible; only polygons which face forwards therefore need to be displayed. Accordingly, a decision is made prior to rendering whether, from the viewing angle concerned, a given polygon is showing its front (outer) or back (inner) face, and only those polygons which are facing forward are rendered. This method of back face culling reduces the problem of hidden surface removal, but does not eliminate the problem altogether.
A further known technique is known as “binary space partitioning” (BSP). In this technique, prior to animation, a pre-processing stage is performed in which a tree-structured model is built in memory, each node in the tree being a polygon on a space partitioning plane and pointing to successor and predecessor nodes (if any) one of the nodes contains a tree consisting of polygons strictly on one side of the partitioning plane, while the other node contains the rest. One can then recursively process the tree (descending first to the node further away from the camera) and render polygons in back to front order.
Another known technique is polygon stripping i.e. to convert independent triangles or polygons into triangle strips. In this technique, a first triangle is identified with an either clockwise or counterclockwise winding, and then all subsequent triangles in the strip will alternate winding. The strip is continued until the triangle strip runs off the edge of the object or runs into a polygon that is already a part of another strip.
Traditionally, due to their extensive consumption of system resources, three-dimensional graphics engines belong to high performance systems such as workstations with powerful processors and large memories. The restrictions posed by limited calculation power are more evident on devices which cannot be provided with the fastest processors. Examples of such devices are mobile phones, personal digital assistants (PDA) and handheld video games. There is therefore a need to provide effective algorithms so that three-dimensional real time animated graphics can be handled by the processing power available in the above-mentioned devices.